import random


class Solution(object):

    def __init__(self, n, blacklist):
        """
        :type n: int
        :type blacklist: List[int]
        """
        self.b = blacklist
        self.m = len(self.b)
        self.num = n - self.m
        self.d = {}
        t = set(self.b)
        self.b.sort()
        index = 0
        for num in range(self.num, n):
            if num not in t:
                self.d[self.b[index]] = num
                index += 1

    def pick(self):
        """
        :rtype: int
        """
        val = random.randint(0, self.num - 1)
        if val not in self.d:
            return val
        else:
            return self.d[val]
